package com.solming.leetcode.question;

import org.springframework.util.CollectionUtils;

import java.util.HashMap;
import java.util.LinkedHashMap;

public class LFUCache460 {
    //键值信息
    private HashMap<Integer, Integer> keyValMap;
    //键对应的使用次数
    private HashMap<Integer, Integer> keyFreqMap;
    //使用次数对应的 key ，使用 LinkedHashMap 是因为其链表结构可以追踪最旧的那个，并且 O(1)查询
    private HashMap<Integer, LinkedHashMap<Integer, Integer>> freqKeyMap;
    //定义的容量
    private int capacity;
    //最小的次数
    private int minFreq;


    public LFUCache460(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        keyValMap = new HashMap<>();
        keyFreqMap = new HashMap<>();
        freqKeyMap = new HashMap<>();
    }

    public int get(int key) {
        if (!keyValMap.containsKey(key)) {
            return -1;
        }
        Integer val = keyValMap.get(key);
        computerFreq(key, val);
        return val;
    }

    public void put(int key, int value) {
        if (this.capacity==0){
            return ;
        }
        if (keyValMap.containsKey(key)) {
            keyValMap.put(key, value);
            computerFreq(key, value);
            return;
        }
        if (keyValMap.size() >= capacity) {
            removeMidAndOld();
        }
        this.minFreq = 1;
        keyValMap.put(key, value);
        keyFreqMap.put(key, 1);
        if (!freqKeyMap.containsKey(1)) {
            freqKeyMap.put(1, new LinkedHashMap<>());
        }
        freqKeyMap.get(1).put(key, value);

    }

    public void removeMidAndOld() {
        Integer key = freqKeyMap.get(minFreq).keySet().iterator().next();
        keyValMap.remove(key);
        keyFreqMap.remove(key);
        freqKeyMap.get(minFreq).remove(key);
        if (freqKeyMap.get(minFreq).isEmpty()){
            freqKeyMap.remove(minFreq);
        }
    }

    /**
     * 计算使用次数
     *
     * @param key
     * @param val
     */
    public void computerFreq(Integer key, Integer val) {
        int freq = keyFreqMap.get(key);
        if (!freqKeyMap.containsKey(freq + 1)) {
            freqKeyMap.put(freq + 1, new LinkedHashMap<>());
        }
        freqKeyMap.get(freq + 1).put(key, val);
        keyFreqMap.put(key, freq + 1);
        freqKeyMap.get(freq).remove(key);
        if (freqKeyMap.get(freq).isEmpty()&&minFreq == freq) {
            minFreq++;
        }
    }

    public static void main(String[] args) {
        LFUCache460 lfuCache460 = new LFUCache460(1);
        lfuCache460.put(0,0);
        System.out.println(lfuCache460.get(0));
    }
}
